package  main.java.leetcode.editor.cn;
//2023-04-06 16:02:02
//给你一个整数 n ，以二进制字符串的形式返回该整数的 负二进制（base -2）表示。 
//
// 注意，除非字符串就是 "0"，否则返回的字符串中不能含有前导零。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 2
//输出："110"
//解释：(-2)² + (-2)¹ = 2
// 
//
// 示例 2： 
//
// 
//输入：n = 3
//输出："111"
//解释：(-2)² + (-2)¹ + (-2)⁰ = 3
// 
//
// 示例 3： 
//
// 
//输入：n = 4
//输出："100"
//解释：(-2)² = 4
// 
//
// 
//
// 提示： 
//
// 
// 0 <= n <= 10⁹ 
// 
// Related Topics 数学 👍 119 👎 0

class ConvertToBase2 {
    public static void main(String[] args) {
        //创建该题目的对象方便调用
        Solution solution = new ConvertToBase2().new Solution();
        solution.baseNeg2(2);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public String baseNeg2(int n) {
        if(n == 0 || n == 1){
            return String.valueOf(n);
        }
        StringBuilder sb = new StringBuilder();
        while (n != 0){
            int val = n & 1;
            sb.append(val);
            n -= val;
            n /= -2;
        }

        return sb.reverse().toString();
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
